package fun.ticsmyc.question;

import org.junit.Test;

import java.util.Arrays;

/**
 * @author Ticsmyc
 * @package fun.ticsmyc.question
 * @date 2020-07-18 17:47
 */
public class 素数 {

    @Test
    public void test(){
        boolean[] isPrim = countPrimes(1000);
        int count =0;
        for (int i = 0; i < isPrim.length; i++) {
            if(isPrim[i])
                count++;
        }
        System.out.println(count);
    }

    public boolean[] countPrimes(int n ){
        boolean[] isPrim = new boolean[n];
        Arrays.fill(isPrim,true);

        for(int i=2 ; i*i<isPrim.length; ++i){
            if (isPrim[i]){
                //i的倍数都不是素数
                for( int j =i*i ;j<isPrim.length; j+=i){
                    isPrim[j] = false;
                }
            }
        }
        return isPrim;
    }
}
